import utils.TreeNode;

import java.util.*;

public class TreeSolutions {
    /**
     * 102. 二叉树的层序遍历
     */
    // 迭代
    public List<List<Integer>> levelOrder_(TreeNode root) {
        List<List<Integer>> lists = new ArrayList<>();
        if (root == null)
            return lists;
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int count = queue.size();
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < count; i++) {
                TreeNode now = queue.poll();
                list.add(now.val);
                if (now.left != null)
                    queue.offer(now.left);
                if (now.right != null)
                    queue.offer(now.right);
            }
            lists.add(list);
        }
        return lists;
    }

    // 递归
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> lists = new ArrayList<>();
        if (root == null)
            return lists;
        dfsLevelOrder(root, 1, lists);
        return lists;
    }

    private void dfsLevelOrder(TreeNode root, int depth, List<List<Integer>> lists) {
        // 如果当前深度大于了lists长度,再加一个数组
        if (lists.size() < depth)
            lists.add(new ArrayList<>());
        // 把当前数字接到对应的list上
        lists.get(depth - 1).add(root.val);
        // dfs递归遍历它的左右子树
        if (root.left != null)
            dfsLevelOrder(root.left, depth + 1, lists);
        if (root.right != null)
            dfsLevelOrder(root.right, depth + 1, lists);
    }

    /**
     * mid 236. 二叉树的最近公共祖先
     */
    // 从上到下递归，返回当前root是否包含p或q
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null)
            return null;
        if (root == p || root == q)
            return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left == p && right == q || left == q && right == p)
            return root;
        if (left == null)
            return right;
        else
            return left;
    }

    // 自p和q向上找父节点，找到第一个重复的就是答案
    public TreeNode lowestCommonAncestor_(TreeNode root, TreeNode p, TreeNode q) {
        // 找到每个节点的父节点
        Map<TreeNode, TreeNode> map = new HashMap<>();
        map.put(root, null);
        findParent(root, map);
        // 从p向上遍历，记录遍历的节点
        Set<TreeNode> set = new HashSet<>();
        while (p != null) {
            set.add(p);
            p = map.get(p);
        }
        // 从q向上遍历，第一个重复的节点即为答案
        while (q != null) {
            if (set.contains(q))
                return q;
            q = map.get(q);
        }
        return null;
    }

    private void findParent(TreeNode root, Map<TreeNode, TreeNode> map) {
        if (root.left != null) {
            map.put(root.left, root);
            findParent(root.left, map);
        }
        if (root.right != null) {
            map.put(root.right, root);
            findParent(root.right, map);
        }
    }

    /**
     * mid 103. 二叉树的锯齿形层序遍历
     */
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> lists = new ArrayList<>();
        if (root == null)
            return lists;
        Deque<TreeNode> queue = new LinkedList<>();
        queue.addFirst(root);
        int level = 1;
        while (!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int size = queue.size();
            // 如果当前level为奇数，是从左往右遍历，把数字加到右面
            if (level % 2 == 1) {
                for (int i = 0; i < size; i++) {
                    TreeNode node = queue.pollFirst();
                    list.add(node.val);
                    if (node.left != null)
                        queue.addLast(node.left);
                    if (node.right != null)
                        queue.addLast(node.right);
                }
            }
            // 如果当前level是偶数，是从右往左遍历，把数字加到左面
            else {
                for (int i = 0; i < size; i++) {
                    TreeNode node = queue.pollLast();
                    list.add(node.val);
                    if (node.right != null)
                        queue.addFirst(node.right);
                    if (node.left != null)
                        queue.addFirst(node.left);
                }
            }
            lists.add(list);
            level++;
        }
        return lists;
    }

    /**
     * hard 124. 二叉树中的最大路径和
     */
    private int ans = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        maxPathSumDFS(root);
        return ans;
    }

    private int maxPathSumDFS(TreeNode root) {
        // 1. left-root-right
        // 2. left-root
        // 3. root-right
        // 4. root
        int val = root.val;
        if (root.left == null && root.right == null) {
            // 4
            ans = Math.max(ans, val);
            return val;
        } else if (root.left == null) {
            // 34
            int right = maxPathSumDFS(root.right);
            int nowMax = Math.max(val, val + right);
            ans = Math.max(ans, nowMax);
            return nowMax;
        } else if (root.right == null) {
            // 24
            int left = maxPathSumDFS(root.left);
            int nowMax = Math.max(val, val + left);
            ans = Math.max(ans, nowMax);
            return nowMax;
        } else {
            // 1234 左右都有子树的情况，最大值考虑1234，但是返回值只考虑234，因为返回值是给父节点参考的，最大值是给答案参考的
            int left = maxPathSumDFS(root.left);
            int right = maxPathSumDFS(root.right);
            int nowMax = Math.max(Math.max(val + left, val + right), Math.max(val, val + left + right));
            int nowReturn = Math.max(Math.max(val + left, val + right), val);
            ans = Math.max(ans, nowMax);
            return nowReturn;
        }
    }

    /**
     * mid 199. 二叉树的右视图
     */
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> queue = new ArrayDeque<>();
        if (root != null)
            queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();
                if (i == size - 1)
                    list.add(poll.val);
                if (poll.left != null)
                    queue.offer(poll.left);
                if (poll.right != null)
                    queue.offer(poll.right);
            }
        }
        return list;
    }

    /**
     * 94. 二叉树的中序遍历
     */
    // 迭代
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            list.add(node.val);
            node = node.right;
        }
        return list;
    }

    // 迭代(无额外空间) morris
    public List<Integer> inorderTraversal_2(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        TreeNode node = root, pre = null;
        while (node != null) {
            // 如果左面为空
            if (node.left == null || node.left == pre) {
                list.add(node.val);
                node = node.right;
                continue;
            }
            // 找到node的前置节点pre
            pre = node.left;
            while (pre.right != null && pre.right != node) {
                pre = pre.right;
            }
            // 如果pre.right为空，连接，node往左
            if (pre.right == null) {
                pre.right = node;
                node = node.left;
            }
            // 如果pre.right是node，断开，遍历node
            else {
                pre.right = null;
                list.add(node.val);
                node = node.right;
            }
        }

        return list;
    }

    /**
     * 144. 二叉树的前序遍历
     */
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        TreeNode node = root;
        Deque<TreeNode> stack = new LinkedList<>();
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                list.add(node.val);
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            node = node.right;
        }
        return list;
    }

    /**
     * 145. 二叉树的后序遍历
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        TreeNode node = root, prev = null;
        Deque<TreeNode> stack = new LinkedList<>();
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stack.push(node);
                prev = node;
                node = node.left;
            }
            node = stack.pop();
            if (node.right == null || prev == node.right) {
                list.add(node.val);
                prev = node;
                node = null;
            } else {
                stack.push(node);
                node = node.right;
            }
        }
        return list;
    }

    /**
     * 105. 从前序与中序遍历序列构造二叉树
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 构建map，找到inorder中值和下标的映射
        int len = inorder.length;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < len; i++)
            map.put(inorder[i], i);
        return buildTreeWithPreAndIn(preorder, inorder, map, 0, len - 1, 0, len - 1);
    }

    private TreeNode buildTreeWithPreAndIn(int[] preorder, int[] inorder, Map<Integer, Integer> map, int preBegin, int preEnd, int inBegin, int inEnd) {
        if (preBegin > preEnd || inBegin > inEnd)
            return null;
        // 找到当前根节点
        TreeNode node = new TreeNode(preorder[preBegin]);
        // 找到左子树和右子树
        int rootPosOfIn = map.get(preorder[preBegin]);
        int leftTreeNodeNum = rootPosOfIn - inBegin;
        int rightTreeNodeNum = inEnd - rootPosOfIn;
        node.left = buildTreeWithPreAndIn(preorder, inorder, map, preBegin + 1, preBegin + leftTreeNodeNum, inBegin, rootPosOfIn - 1);
        node.right = buildTreeWithPreAndIn(preorder, inorder, map, preBegin + leftTreeNodeNum + 1, preEnd, rootPosOfIn + 1, inEnd);
        return node;
    }

    /**
     * mid 129. 求根节点到叶节点数字之和
     */
    public int sumNumbers(TreeNode root) {
        return getSumNumbers(root, 0);
    }

    private int getSumNumbers(TreeNode root, int val) {
        int newVal = val * 10 + root.val;
        if (root.left == null && root.right == null)
            return newVal;
        int sum = 0;
        if (root.left != null)
            sum += getSumNumbers(root.left, newVal);
        if (root.right != null)
            sum += getSumNumbers(root.right, newVal);
        return sum;
    }

    /**
     * easy 104. 二叉树的最大深度
     */
    public int maxDepth(TreeNode root) {
        if (root == null)
            return 0;
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        return Math.max(leftDepth, rightDepth) + 1;
    }

    public int maxDepth_(TreeNode root) {
        if (root == null)
            return 0;
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        int depth = 0;
        while (!queue.isEmpty()) {
            depth++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null)
                    queue.offer(node.left);
                if (node.right != null)
                    queue.offer(node.right);
            }
        }
        return depth;
    }

    /**
     * easy 110. 平衡二叉树
     */
    boolean isBalanceTree = true;

    public boolean isBalanced(TreeNode root) {
        int temp = getHeightTree(root);
        return isBalanceTree;
    }

    private int getHeightTree(TreeNode node) {
        if (node == null)
            return 0;
        int left = getHeightTree(node.left);
        int right = getHeightTree(node.right);
        if (Math.abs(left - right) > 1)
            isBalanceTree = false;
        return Math.max(left, right) + 1;
    }

    /**
     * mid 98. 验证二叉搜索树
     */
    public boolean isValidBST(TreeNode root) {
        return isValid(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean isValid(TreeNode root, long small, long big) {
        if (root == null)
            return true;
        boolean left = isValid(root.left, small, root.val);
        boolean right = isValid(root.right, root.val, big);
        return left && right && root.val < big && root.val > small;
    }

    /**
     * 543. 二叉树的直径
     */
    int maxDiameter = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        getMaxDiameter(root);
        return maxDiameter;
    }

    private int getMaxDiameter(TreeNode root) {
        // 这个方法返回当前节点为root的最大高度
        if (root == null)
            return 0;
        int left = getMaxDiameter(root.left);
        int right = getMaxDiameter(root.right);
        maxDiameter = Math.max(left + right, maxDiameter);
        return Math.max(left, right) + 1;
    }

    /**
     * 662. 二叉树最大宽度
     */
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null)
            return 0;
        Deque<TreeNode> queue = new ArrayDeque<>();
        Deque<Long> index = new ArrayDeque<>();
        queue.offer(root);
        index.offer(1L);
        long maxAns = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            long min = Long.MAX_VALUE;
            long max = Long.MIN_VALUE;
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                long idx = index.poll();
                min = Math.min(min, idx);
                max = Math.max(max, idx);
                // 下一层
                if (node.left != null) {
                    queue.offer(node.left);
                    index.offer(idx * 2);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                    index.offer(idx * 2 + 1);
                }
            }
            maxAns = Math.max(maxAns, max - min + 1);
        }
        return (int) maxAns;
    }

    /**
     * 113. 路径总和 II
     */
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> lists = new ArrayList<>();
        if (root == null)
            return lists;
        getPathSum(root, targetSum, lists, new ArrayList<>());
        return lists;
    }

    private void getPathSum(TreeNode root, int target, List<List<Integer>> lists, List<Integer> list) {
        target -= root.val;
        if (target == 0 && root.left == null && root.right == null) {
            list.add(root.val);
            lists.add(new ArrayList<>(list));
            list.remove(list.size() - 1);
            return;
        }
        if (root.left != null) {
            list.add(root.val);
            getPathSum(root.left, target, lists, list);
            list.remove(list.size() - 1);
        }
        if (root.right != null) {
            list.add(root.val);
            getPathSum(root.right, target, lists, list);
            list.remove(list.size() - 1);
        }
    }

    /**
     * 112. 路径总和
     */
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null)
            return false;
        targetSum -= root.val;
        if (root.left == null && root.right == null)
            return targetSum == 0;
        boolean left = hasPathSum(root.left, targetSum);
        boolean right = hasPathSum(root.right, targetSum);
        return left || right;
    }

    /**
     * 226. 翻转二叉树
     */
    public TreeNode invertTree(TreeNode root) {
        if (root == null)
            return null;
        TreeNode l = invertTree(root.left);
        TreeNode r = invertTree(root.right);
        root.left = r;
        root.right = l;
        return root;
    }
}
